Modern learning algorithms use gradient descent updates to train inferentialmodels that best explain data. Scaling these approaches to massive data sizesrequires proper distributed gradient descent schemes where distributed workernodes compute partial gradients based on their partial and local data sets, andsend the results to a master node where all the computations are aggregatedinto a full gradient and the learning model is updated. However, a majorperformance bottleneck that arises is that some of the worker nodes may runslow. These nodes a.k.a. stragglers can significantly slow down computation asthe slowest node may dictate the overall computational time. We propose adistributed computing scheme, called Batched Coupon's Collector (BCC) toalleviate the effect of stragglers in gradient methods. We prove that our BCCscheme is robust to a near optimal number of random stragglers. We alsoempirically demonstrate that our proposed BCC scheme reduces the run-time by upto 85.4% over Amazon EC2 clusters when compared with other straggler mitigationstrategies. We also generalize the proposed BCC scheme to minimize thecompletion time when implementing gradient descent-based algorithms overheterogeneous worker nodes.
展开▼
